# -*- coding: utf-8 -*-
import collections;

# 给出一个区间的集合，请合并所有重叠的区间

# 示例 1:
# 输入: [[1,3],[2,6],[8,10],[15,18]]
# 输出: [[1,6],[8,10],[15,18]]
# 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]

# 示例 2:
# 输入: [[1,4],[4,5]]
# 输出: [[1,5]]
# 解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间





# # 记录解题思路，以及思路的误区
# # 把区间转换为点，并且给点增加上属性
# # eg: [1,3],[2,6],[8,10],[15,18]
# # 1"b" 2"b" 3"e" 6"e" 8"b" 10"e" 15"b" 18"e"
# # 如上所示
# # 从第1个"b"找到最后1个"e"  1"b" 2"b" 3"e" 6"e" [1-6]
# # 
# # 误区1:
# # 未考虑同一个点具有多个属性的情况
# # eg: [1,4],[2,4],[4,5]
# # 尝试使用"b"属性覆盖"e"来解决
# # 1"b" 2"b" 4"b" 5"e"
# # 
# # 误区2：
# # 解决误区1后，未考虑单点区间的问题
# # eg [1,4],[5,5],[7,8]
# # 按照误区1生成的属性是
# # 1"b" 4"e" 5"b" 7"b" 8"e"
# # 结果合并出错误的区间[5, 8]
# # 尝试的解决方案，增加新属性"be",并且"b","e"都能覆盖掉"be"
# # 则重新生成后的属性是
# # "1b" "4e" 5"be" 7"b" 8"e"
# # 如果在只找到"b"的情况下遇到"be"可以直接把"be"忽略掉
# # 其他情况下"be"独立形成区间[5,5]
# # 
# # 误区3：
# # 误区1，误区2是少考虑某些情况
# # 误区3则是算法本身的错误
# # 未考虑多重交叉的情况
# # eg: [1,4],[0,2],[3,5]
# # 生成属性是
# # 0"b" 1"b" 2"e" 3"b" 4"e" 5"e"
# # 按照算法生成的是[0,2],[3,5]显然是不正确的
# # 
# # 误区4：
# # 由误区3可知同时对多个进行合并会出错误，那么每一次只合并2个是否能解决问题呢
# # eg: [1,4],[0,2],[3,5]
# # 1、[1,4],[0,2] => [0,4]
# # 2、[0,4],[3,5] => [0,5]
# # 貌似是可以的但是，仍然有没考虑到的情况
# # eg: [[2,3],[4,5],[1,10]]
# # 1、[2,3],[4,5] => [2,3],[4,5]
# # 2、[[2,3],[4,5],[1,10]]仍然要进行同时多个进行合并，又回归到误区3
# # 
# # 整体思路有问题，所以这个解决方案是错误的
# # 思考错误的原因：
# # 算法思路中是有信息丢失的
# # 只考虑了区间的顶点属性
# # eg: [0,3] => 0b,3e
# # 但是却丢失了[0,3]是连通在一起构成区间的这条信息
# # 算法的数据结构和流程上都没有考虑到上面这条信息，所以思路是错误的
# class Solution(object):
#     def merge(self, intervals):
#         """
#         :type intervals: List[List[int]]
#         :rtype: List[List[int]]
#         """
#         if not intervals:
#             return [];

#         points = {};

#         for i in range(len(intervals)):
#             signal_interval = intervals[i];

#             if signal_interval[0] == signal_interval[1]:
#                 if not points.has_key( signal_interval[0] ):
#                     points[ signal_interval[0] ] = "be";
#                 continue;

#             points[ signal_interval[0] ] = "b";

#             if not points.has_key( signal_interval[1] ):
#                 points[ signal_interval[1] ] = "e";
        
#         keys = points.keys();
#         keys.sort();

#         rtn = [];
#         signal_rtn = [];
#         for key in keys:
#             if points[key] == "be":
#                 if len(signal_rtn) != 1:
#                     rtn.append([key, key]);
#                 continue;

#             if points[key] == "b":
#                 if not signal_rtn:
#                     signal_rtn.append(key);
#                 elif len(signal_rtn) == 2:
#                     rtn.append(signal_rtn);
#                     signal_rtn = [];
#                     signal_rtn.append(key);

#             if points[key] == "e":
#                 if len(signal_rtn) == 1:
#                     signal_rtn.append(key);
#                 else:
#                     signal_rtn[1] = key;

#         rtn.append(signal_rtn);

#         return rtn;







# # 查看官方解答后，整理出的答案，超出时间限制
# # 
# # 使用list来表示区间
# # eg: [0,10],[1,4]
# # 如上2个区间合并后表示为
# # [0,10,1,4]可以通过找出list中min,max来确定区间[min, max]
# # 
# # 使用无向图来构建区间之间的关系
# # [1,5],[4,7],[6,10],[15,17],[16,20]
# # 构建无向图后表示为
# # (1,5)  ->  (4,7)
# # (4,7)  ->  (1,5),(6,10)
# # (6,10) ->  (4,7)
# # (15,17)->  (16,20)
# # (16,20)->  (15,17)
# # 然后整理出连通的区域
# # (1,5)->(4,7)->(6,10)
# # (15,17)->(16,20)
# # 每一个连通区域都代表着一个可以合并的区间
# # [1,5,4,7,6,10] [15,17,16,20]
# class Solution(object):
#     def merge(self, intervals):
#         """
#         :type intervals: List[List[int]]
#         :rtype: List[List[int]]
#         """

#         if not intervals:
#             return [];

#         def is_overlap(p1, p2):
#             return not (p1[0] > p2[1] or p1[1] < p2[0]);

#         def build():
#             for i in range(len(intervals)):
#                 for j in range(i + 1, len(intervals)):
#                     if is_overlap(intervals[i], intervals[j]):
#                         graph[tuple(intervals[i])].append( tuple(intervals[j]) );
#                         graph[tuple(intervals[j])].append( tuple(intervals[i]) );

#         def get_components():
#             visited = set();
#             components = [];

#             def make_component_dps(node):
#                 stack = [] + list(node);
#                 for i in range(len(graph[node])):
#                     if graph[node][i] in visited:
#                         continue;
#                     visited.add(graph[node][i]);
#                     stack = stack + make_component_dps(graph[node][i]);
#                 return stack;


#             for interval in intervals:
#                 interval = tuple(interval);
#                 if interval in visited:
#                     continue;
#                 visited.add(interval);
#                 components.append( make_component_dps(interval) );

#             return components;

#         graph = collections.defaultdict(list);
#         build();
#         components = get_components();

#         rtn = [];
#         for i in range(len(components)):
#             rtn.append([min( components[i] ), max( components[i] )]);

#         return rtn;








# 笑哭！以下思路，简单好记速度快，可是这一道题，折腾将近一天
# 解题思路：
# 按照区间的 start 大小排序，那么在这个排序的列表中可以合并的区间一定是连续的
# eg:
# [1,9],[2,5],[19,20],[10,11],[12,20],[0,3],[0,1],[0,2]
# 排序后
# [0,3],[0,1],[0,2],[1,9],[2,5],[10,11],[12,20],[19,20]
#  ----------------------------  -----   ------------- 
# 可以看到可以合并的区间一定是连续在一起的
class Solution(object):
    def merge(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: List[List[int]]
        """

        intervals.sort(key = lambda p : p[0]);

        rtn = [];
        for i in range(len(intervals)):
            interval = intervals[i];
            if not rtn or interval[0] > rtn[-1][1]:
                rtn.append(interval);
            else:
                rtn[-1][1] = max(rtn[-1][1], interval[1]);
        return rtn;
t = Solution();
print t.merge([[1,9],[2,5],[19,20],[10,11],[12,20],[0,3],[0,1],[0,2]]);